// 给定一个二叉树，它的每个结点都存放一个 0-9 的数字，每条从根到叶子节点的路径都代表一个数字。
// 例如，从根到叶子节点路径 1->2->3 代表数字 123。
// 计算从根到叶子节点生成的所有数字之和。
// 说明: 叶子节点是指没有子节点的节点。


const sumNumbers = function (root: TreeNode | null): number {
    let sum: number = 0;// 结果和
    let currStr = '';// 当前字符串
    // 安全检测
    if (root === null) {
        return sum;
    }
    // 深度优先遍历辅助函数
    function sumNumbers_DFS(root: TreeNode) {
        currStr += root.val;// 走进新节点当前长度即加和
        // 注意！如何判断走进叶节点
        if (root.left === null && root.right === null) {
            sum += Number(currStr);
            currStr = currStr.substring(0, currStr.length - 1);// 截去最后一个字符
            return;
        }
        // 判断是否存在左右节点
        if (root.left) {
            sumNumbers_DFS(root.left);
        }
        if (root.right) {
            sumNumbers_DFS(root.right);
        }
        // 注意！左右子树走完后当前这个节点值其实也没用了，也需要截去
        currStr = currStr.substring(0, currStr.length - 1);
    }
    sumNumbers_DFS(root);
    return sum;
};

// 测试用例
let sumNumbers_test = {
    val: 4,
    left: {
        val: 9,
        left: {
            val: 5,
            left: null,
            right: null
        },
        right: {
            val: 1,
            left: null,
            right: null
        }
    },
    right: {
        val: 0,
        left: null,
        right: null
    }
}

sumNumbers(sumNumbers_test);


// 这道题目是一道深度优先搜索路径相关的题目
// 思路并不难想，但是细节要注意
// 首先将路径和总和作为闭包变量
// 在深度优先遍历的过程中需要不断地检测并保证传入DFS的函数是正常的节点
// 这里需要注意的有两个地方，使用左右节点为空条件可以判断当前节点是叶节点
// 而当走完叶节点后需要截去最后一个字符串
// 此外当左右子树遍历完之后，当前的这个节点的任务其实也完成了
// 在这个位置也需要截去最后一个字符串。